#include <iostream>
#include <vector>

using namespace std;

// 时间复杂度O(n)
int searchInsert(vector<int>& nums, int target) {
    for (int i = 0, len = nums.size(); i < len; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }

    return nums.size();
}

// 时间复杂度O(logn) [a, b]
int searchInsert1(vector<int>& nums, int target) {
    int len = nums.size();
    int left = 0, right = len - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }

    // whiel循环之后left
    return right + 1;
}

// 时间复杂度O(logn) [a, b)
int searchInsert2(vector<int>& nums, int target) {
    int len = nums.size();
    int left = 0, right = len;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > target) {
            right = middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }

    return right;
}

int main() {
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 10;
    int result = searchInsert2(nums, target);

    cout << "reslut: " << result << endl;
}